package org.example.myleet.p522;

/**
 * 官方解法：反证法
 * 考虑这种情况：str[i]的子序列sub是strs的特殊子序列，则由sub通过插入或拼接字符形成的字符串str[i]也是strs的特殊子序列
 * 因为题目要求的sub是strs的特殊子序列的意思可以理解成sub只在strs中出现过一次，
 * 那么sub无论添加多少个字符串形成的新字符串str[i]也只会在strs中出现过一次
 * 因此只要证明str[i]不是任何其他str[j]的子串，那么就可以证明str[i]是特殊子序列
 */
public class Solution {
    public int findLUSlength(String[] strs) {
        int maxUSLen = -1;
        for (int i = 0; i < strs.length; ++i) {
            //strs[i]与所有strs[j]比较后如果都不是strs[j]的子串，则strs[i]是特殊子串
            boolean isUniqueSubsequence = true;
            for (int j = 0; j < strs.length; ++j) {
                if (i == j) {
                    continue;
                }
                if (isSubSequence(strs[i], strs[j])) {
                    //只要strs[i]是strs[j]的子串，则strs[i]一定不是特殊子序列
                    isUniqueSubsequence = false;
                }
            }
            if (isUniqueSubsequence) {
                //如果
                maxUSLen = Math.max(maxUSLen, strs[i].length());
            }
        }
        return maxUSLen;
    }

    /**
     * 双指针+贪心
     * sub和str各一个指针，匹配到字符则两个指针往前，否则就str指针往前
     * 遍历完成后如果sub的指针也到达尾部，说明sub是str的子串，否则不是
     */
    private boolean isSubSequence(String sub, String str) {
        if (sub.length() > str.length()) {
            //子串要求长度不超过原字符串
            return false;
        }
        int i = 0, j = 0;
        while (j < str.length()) {
            if (sub.charAt(i) == str.charAt(j)) {
                ++i;
            }
            if (i >= sub.length()) {
                return true;
            }
            ++j;
        }
        return i == sub.length();
    }
}
